#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
    static bool check(const std::vector<int>& position, int m, int d) {
        int cnt = 1;  
        int pre = position[0];
        for (size_t i = 0; i < position.size(); ++i) {
            int p = position[i];
            if (p >= pre + d) {
                cnt++; 
                pre = p; 
            }
        }
        return cnt >= m;
    }
    int maxDistance(std::vector<int>& position, int m) {
        std::sort(position.begin(), position.end()); 
        int t = 0;
        int r = position.back();
        while (t <= r) {
            int mid = t + (r - t) / 2;
            if (check(position, m, mid)) {
                t = mid + 1;
            } else {
                r = mid - 1;  
            }
        }
        return t - 1;
    }
};
int main() {
    Solution sol;
    std::vector<int> position;
    position.push_back(1);
    position.push_back(2);
    position.push_back(3);
    position.push_back(4);
    position.push_back(7);
    int m = 3;
    int result = sol.maxDistance(position, m);
    std::cout << "The maximum distance is: " << result << std::endl;
    return 0;
}

